#40冗余覆盖子串
# s1 = list(map(lambda x:ord(x),input()))
# s2 = list(map(lambda x:ord(x),input()))
# k = int(input())
# if len(s2) < len(s1) + k:
#     print(-1)
#     exit()
# count = [0] * 128
# for c in s1:
#     count[c] += 1
#
# total = len(s1)
# for i in range(len(s2)):
#     rc = s2[i]
#     if count[rc] > 0:
#         total -= 1
#     count[rc] -= 1
#     if i >= len(s1)+k:
#         lc = s2[i-len(s2)-k+1]
#
#         if count[lc] >= 0:
#             total += 1
#         count[lc] += 1
#     if total == 0:
#         print(max(0,i - len(s1) - k + 1))
#         break
# print(-1)

#41贪心的商人
# number = int(input())
# days = int(input())
# item = list(map(int, input().split()))
# item_price = [list(map(int, input().split())) for _ in range(number)]
#
# ans = 0
#
# for i in range(number):
#     for j in range(days - 1):
#         ans += max(item_price[i][j + 1] - item_price[i][j], 0) * item[i]
#
# print(ans)

#42工作安排优化算法
# time,n = map(int,input().split())
# lst = [list(map(int,input().split())) for _ in range(n)]
# print(lst)
# # dp = [[0] * (time+1)] * (n+1)
# # print(dp)
# dp = [[0 for j in range(time+1)] for i in range(n+1)]
# print(dp)
# for i in range(1,n+1):
#     t,w = lst[i - 1]
#     for j in range(1,time+1):
#         if t > j:
#             dp[i][j] = dp[i-1][j]
#         else:
#             dp[i][j] = max(dp[i-1][j],w + dp[i-1][j-t])
#
# print(dp[-1][-1])
# 输入获取
# T, n = map(int, input().split())
# tws = [list(map(int, input().split())) for i in range(n)]
# # 算法入口
# def getResult():
#     dp = [0] * (T + 1)
#
#     # 01背包问题滚动数组优化
#     for i in range(1, n + 1):
#         t, w = tws[i - 1]
#         # 注意背包承重遍历必须倒序，正序的话就变成完全背包了
#         for j in range(T, t - 1, -1):
#             dp[j] = max(dp[j], dp[j - t] + w)
#
#     return dp[T]
# # 算法调用
# print(getResult())

#43简单的像素曝光
# import sys
# nums = list(map(int, input().split()))
# n = len(nums)
#
# minDiff = sys.maxsize
# minK = sys.maxsize
# for k in range(-127, 129):
#     newImgSum = 0
#     for num in nums:
#         # 新图的像素值会自动截取到[0,255]范围。当新像素值<0，其值会更改为0；当新像素值>255，其值会更改为255
#         newImgSum += min(max(num + k, 0), 255)
#
#     # 新图片所有像素平均值为 avg
#     avg = newImgSum / n
#
#     # diff越小，新图片平均像素值越接近128
#     diff = abs(avg - 128)
#     if diff < minDiff:
#         minDiff = diff
#         minK = k
# print(minK)

#44预定酒店
# if __name__ == '__main__':
#     n, k, x = map(int, input().split())
#     A = list(map(int, input().split()))
#     arr = list(map(lambda a : (a,abs(a-x)),A))
#     print(arr)
#     arr.sort(key = lambda a:(a[1],a[0]))
#     print(arr)
#     res = []
#     for i in range(k):
#         res.append(arr[i][0])
#     print(res)
#     # res = list(map(lambda a:a[0],arr[:k]))
#     res.sort()
#     ret =  map(int, res)
#     print(res)
#     # print(' '.join(map(str,res)))

#45数组找数字
# n = int(input())
# m = int(input())
# matrix = [list(map(int,input().split())) for _ in range(n)]
# nums = {}
# for i in range(n):
#     for j in range(m):
#         num = matrix[i][j]
#         if nums.get(num) is None:
#             nums[num] =[ [i,j]]
#         else:
#             nums[num].append([i,j])
#
# for i in range(n):
#     for j in range(m):
#         num = matrix[i][j]
#         midDis = sys.maxsize
#         for i1,j1 in nums[num]:
#             if i1 != i or j1 != j:
#                 midDis = min(midDis,abs(i1-i)+abs(j1-j))
#         matrix[i][j] = -1 if midDis == sys.maxsize else midDis
# print(matrix)

#46猜字谜
# issues = input().split(',')
# answers = input().split(',')
# def getDistinctStr(s):
#     occurs = set()
#     lst = []
#     for c in s:
#         if c not in occurs:
#             lst.append(c)
#             occurs.add(c)
#     return  ''.join(lst)
# distinct_issues = list(map(lambda x:getDistinctStr(x),issues))
# sorted_issues = list(map(lambda x:''.join(sorted(list(x))),issues))

#47 猜数字
# def getRet(s,guess):
#     x = 0
#     y = 0
#     guessList = []
#     answerList = []
#     for j in range(4):
#         if guess[j] == ans[j]:
#             x += 1
#         else:
#             guessList.append(guess[j])
#             answerList.append(guess[j])
#     for c in guessList:
#         if c in answerList:
#             y+=1
#             answerList.remove(c)
#     return f"{x}A{y}B"
# n = int(input())
# guesses = []
# rets = []
# for _ in range(n):
#     guess,ret = input().split()
#     guesses.append(guess)
#     rets.append(ret)
# ans = []
#
# for i in range(0,10000):
#     s  = str(i)
#     while len(s) < 4:
#         s += '0'
#     gu = 0
#     while gu < len(guesses):
#         if rets[i] != getRet(s,guesses[i]):
#             break
#         gu += 1
#
#     if gu == len(guesses):
#         ans.append(s)
#
# if len(ans) != 1:
#     print('NA')
# else:
#     print(ans[0])

#48单词接龙
# k = int(input())
# n = int(input())
# words = [input() for _ in range(n)]
#
# #第K个作为首单词
# # chain = [words.pop(k)]
# chain = words.pop(k)
# prefix = {}
# for word in words:
#     w = word[0]
#     if prefix.get(w) is None:
#         prefix[w] = []
#     prefix[w].append(word)
#
# for w in prefix.keys():
#     prefix[w].sort(key = lambda x:(-len(x),x))
#
# while True:
#     # tail = chain[-1][-1]
#     tail = chain[-1]
#     if tail not in prefix or len(prefix[tail]) == 0:
#         break
#     # chain.append(prefix[tail].pop(0))
#     chain += prefix[tail].pop(0)
# print(chain)
# # print(''.join(chain))

#49水仙花数
# n = int(input())
# m = int(input())
# def solution():
#     if n < 3 or n > 7 or m < 0:
#         return -1
#
#     dic = {
#         3: [153, 370, 371, 407],
#         4: [1634, 8208, 9474],
#         5: [54748, 92727, 93084],
#         6: [548834],
#         7: [1741725, 4210818, 9800817, 9926315]
#     }
#     if m < len(dic[n]):
#         return dic[n][m]
#     else:
#         return dic[n][-1] * m
# print(solution())

#50We are a team
# 输入获取
# n, m = map(int, input().split())
# msgs = [list(map(int, input().split())) for _ in range(m)]
# # 并查集实现
# class UnionFindSet:
#     def __init__(self, n):
#         self.fa = [i for i in range(n)]
#     def find(self, x):
#         if self.fa[x] != x:
#             self.fa[x] = self.find(self.fa[x])
#             return self.fa[x]
#         return x
#     def union(self, x, y):
#         x_fa = self.find(x)
#         y_fa = self.find(y)
#         if x_fa != y_fa:
#             self.fa[y_fa] = x_fa
# def getResult():
#     # 如果第一行 n 和 m 的值超出约定的范围时，输出字符串”Null“。
#     # 1<=n,m<100000
#     if n < 1 or n >= 100000 or m < 1 or m >= 100000:
#         print("NULL")
#         return
#     ufs = UnionFindSet(n + 1)
#
#     for a, b, c in msgs:
#         if a < 1 or a > n or b < 1 or b > n:
#             # 当前行 a 或 b 的标号小于 1 或者大于 n 时，输出字符串‘da pian zi‘
#             print("da pian zi")
#             continue
#         if c == 0:
#             # c == 0 代表 a 和 b 在一个团队内
#             ufs.union(a, b)
#         elif c == 1:
#             # c == 1 代表需要判定 a 和 b 的关系，如果 a 和 b 是一个团队，输出一行’we are a team’,如果不是，输出一行’we are not a team’
#             print("we are a team" if ufs.find(a) == ufs.find(b) else "we are not a team")
#         else:
#             # c 为其他值，输出字符串‘da pian zi‘
#             print("da pian zi")
# getResult()

#51字符重新排序
# s = input()
# dic = {}
# for c in s:
#     dic[c] = dic.get(c,0) + 1
#
# keys = sorted(dic.keys(),key = lambda x:(-dic[x],ord(x)-(97 if x.islower() else 0)))

#52计算堆栈中剩余数字
# def push(num,stack):
#     total = num
#     for i in range(len(stack) - 1, -1, -1):
#         total -= stack[i]
#         if total == 0:
#             del stack[i:]
#             push(num * 2,stack)
#             return
#         elif total < 0:
#             break
#     stack.append(num)
# nums = list(map(int,input().split()))
# stack = [nums[0]]
# for i in range(1,len(nums)):
#     push(nums[i],stack)
#
# stack.reverse()
# print( ' '.join(map(str,stack)))

#53报数
# from collections import deque
#
# # 输入获取
# m = int(input())
# # 核心代码
# def solution():
#     if m <= 1 or m >= 100:
#         return "ERROR!"
#     que = deque([i for i in range(1, 101)])
#     num = 1
#     while len(que) >= m:
#         id = que.popleft()
#         if num == m:
#             num = 1
#         else:
#             num += 1
#             que.append(id)
#     lst = list(que)
#     lst.sort()
#     return ",".join(map(str, lst))
# # 输出打印
# print(solution())

#54工号系统
# math.ceil(math.log10(x/math.pow(20,y)))

#55第K个排列
# n = int(input())
# k = int(input())
#
# nums = []
# fact = 1
# for i in range(1,n+1):
#     fact *= i
#     nums.append(i)
#
# res = []
#
# k-= 1
#
# for i in range(n,0,-1):
#     fact //= i
#     res.append(nums.pop(k // fact))
#     k %= fact
#
# print(''.join(map(str,res)))

#56恢复数字序列
# def inc(num,ans):
#     while num > 0:
#         i = num % 10
#         num = num // 10
#         ans[i]+=1
#     return ans
#
# def dec(num,ans):
#     while num > 0:
#         i = num % 10
#         num = num // 10
#         ans[i]-=1
#         return ans
# def eql(digit,ans):
#     for i in range(len(digit)):
#         if digit[i] != ans[i]:
#             return False
#     return True
#
# digit = [0] * 10
# s, k = input().split()
# k = int(k)
# for c in s:
#     digit[int(c)] += 1
# print(digit)
# for i in range(0,1001):
#     pass
#
# ans = [0] * 10
# for i in range(1,k+1):
#     inc(i,ans)
#     if eql(digit,ans):
#         print(1)
#         exit(0)
#
# for i in range(k+1,10001):
#     inc(i,ans)
#     dec(i - k,ans)
#     if eql(digit,ans):
#         print(i-k+1)
#         exit(0)
# print(-1)

#57 vlan资源池
# vlan = [0] * 4096
#
# vl = input().split(',')
# req = int(input())
# # vl = list(map(lambda x:list(map(int,x.split('-'))),input().split(',')))
# for i in range(len(vl)):
#     arr = vl[i].split('-')
#     start =int(arr[0])
#     end = int(arr[0])if len(arr) == 1 else int(arr[1])
#     for j in range(start,end+1):
#         vlan[j] = 1
# vlan[req] = 0
# res = []
#
# l = 1
# while l < 4095:
#     if vlan[l] == 1:
#         for r in range(l+1,4095):
#             if vlan[r] == 1:
#                 continue
#
#             if  l == r - 1:
#                 res.append(str(l))
#             else:
#                 res.append(f"{l}-{r-1}")
#             l  = r
#             break
#     l +=1
#
#
# print(','.join(res))

#58选修课
# class1 = {}
# class2 = {}
# students = input().split(';')
# for idx,score in students:
#     class1[idx] = score
# students = input().split(';')
# for idx,score in students:
#     class2[idx] = score
#
# classes = {}
# for studID in class1:
#     if studID in class2:
#         classId = studID[:5]
#         classes.setdefault(classId,[])
#         classes[classId].append(studID)
#
# if len(classes) == 0:
#     print("NULL")
#
# for classId  in sorted(classes.keys()):
#     classes[classId].sort(key = lambda  x: (-(class1[x] + class2[x]) ,x))
#     print(classId)
#     print(';'.join(classes[classId]))

#59关联子串
# def solution():
#     # 由于字符串s1中都是小写字母，因此每个字母的ASCII码范围是97~122，因此这里初始化128长度数组来作为统计容器
#     count = [0] * 128
#     for c in s1:  # 统计s1中所有每个字符出现的次数到count中
#         count[c] += 1#
#     # s1字符总数
#     total = len(s1)
#
#     # i 作为滑窗的右边界
#     # 当 i < s1.length 时，滑窗范围是：[0, i]
#     # 当 i ≥ s1.length 是，滑窗范围是：[i - s1.length + 1, i]，保证滑窗长度为：s1.length
#     for i in range(len(s2)):
#         rc = s2[i]  # 滑窗新增的字符（右边界字符）
#
#         if count[rc] > 0:
#             total -= 1
#         count[rc] -= 1
#
#         if i >= len(s1):
#             lc = s2[i - len(s1)]  # 滑窗需要移除的字符（左边界字符）
#
#             if count[lc] >= 0:
#                 total += 1
#             count[lc] += 1
#
#         if total == 0:
#             return i - len(s1) + 1
#
#     return -1
# if __name__ == '__main__':
#     s1, s2 = map(lambda s: list(map(lambda c: ord(c), s)), input().split())
#     print(solution())


#60游戏分组
# arr = list(map(int,input().split()))
# arr.sort()
# def dfs(arr,index,level,sum,res):
#     if level == 5:
#         res.append(sum)
#         return
#     for i in range(index,10):
#         if i > index and arr[i] == arr[i-1]:
#             continue
#         dfs(arr,index+1,level+1,sum+arr[i],res)
#
# res =[]
# sumV = sum(arr)
# dfs(arr,0,0,0,res)
# print(min(map(lambda x: abs((sumV-x) - x),res)))

#61分割数组最大差值
# arr = list(map(int,input().split()))
# right = sum(arr) - arr[0]
# left = arr[0]
# diff = abs(right - left)
#
# for i in range(1,len(arr)-1):
#     left += arr[i]
#     right -= arr[i]
#     diff = max(diff, abs(left-right))

#62货币转换
# import re
# # 输入获取
# n = int(input())
# lines = [input() for _ in range(n)]
# def solution():
#     pattern = r"(\d+)(CNY|JPY|HKD|EUR|GBP|fen|cents|sen|eurocents|pence)"
#
#     exChange = {
#         "CNY": 100,
#         "JPY": 100 / 1825 * 100,
#         "HKD": 100 / 123 * 100,
#         "EUR": 100 / 14 * 100,
#         "GBP": 100 / 12 * 100,
#         "fen": 1,
#         "cents": 100 / 123,
#         "sen": 100 / 1825,
#         "eurocents": 100 / 14,
#         "pence": 100 / 12
#     }
#     ans = 0
#     for line in lines:
#         result = re.findall(pattern, line)
#         for amount, unit in result:
#             ans += int(amount) * exChange[unit]
#     return int(ans)
#
# # 输出打印
# print(solution())


#63荒岛逃生
# nums = list(map(int,input().split()))
# negative = 0
# positive = []
# for num in nums:
#     if num == 0:
#         print(-1)
#         exit()
#     if num > 0:
#         positive.append(num)
#     else:
#         while True:
#             if len(positive) == 0:
#                 negative += 1
#                 break
#
#             pk = num + positive.pop()
#             if pk < 0:
#                 num = pk
#             elif pk > 0:
#                 positive.append(pk)
#                 break
#             else:
#                 break

#64查找接口成功率最优时间段
# minAverageLost = int(input())
# nums = list(map(int, input().split()))
# # 算法入口
# def getResult():
#     n = len(nums)
#     preSum = [0] * (n + 1)
#     for i in range(1, n + 1):
#         preSum[i] = preSum[i - 1] + nums[i - 1]
#     ans = []
#     maxLen = 0
#     for i in range(n):
#         for j in range(i + 1, n + 1):
#             # sumV 是 区间 [i, j-1] 的和
#             sumV = preSum[j] - preSum[i]
#             length = j - i
#             lost = length * minAverageLost
#
#             if sumV <= lost:
#                 if length > maxLen:
#                     ans = [[i, j - 1]]
#                     maxLen = length
#                 elif length == maxLen:
#                     ans.append([i, j - 1])
#
#     ans.sort(key=lambda x: x[0])
#
#     if len(ans) == 0:
#         return "NULL"
#     else:
#         return " ".join(map(lambda x: "-".join(map(str, x)), ans))


#65根据某条件聚类最少交换次数
# nums = list(map(int,input().split()))
# n = int(input())
# window = 0
# for num in nums:
#     if num < n :
#         window += 1
#
# minSwap = len(nums)
# swap = 0
# for r in range(len(nums)):
#     if nums[r] >= n:
#         swap += 1
#
#     if r >= window and nums[r-window+1] >= n:
#         swap -= 1
#
#     if r >= window - 1:
#         minSwap = min(minSwap,swap)
#prtin(minSwap)

#66数字涂色
# digit = list(map(int,input().split()))
# n = len(digit)
# digit.sort()
# count = 0
# color = [False] * len(digit)
# for i in range(len(digit)):
#     if color[i]:
#         continue
#     color[i] = True
#     for j in range(i+1,n):
#         if not color[j]  and color[j] % color[i] == 0:
#             color[j] = True
#     count+=1

#67IPV4转换
# def solution(s):
#     addrs = s.split("#")
#     # ip不是由4个小节组成, 则抛出异常
#     if len(addrs) != 4:
#         return "invalid IP"
#     # 每小节的取值范围
#     ranges = ((1, 128), (0, 255), (0, 255), (0, 255))
#
#     # 记录结果十六进制串
#     hexLst = []
#     for i in range(4):
#         # 如果这一小节转整型失败（包括空串, 非数字串等情况），则非法
#         try:
#             num = int(addrs[i])
#         except:
#             return "invalid IP"
#         # 非0的但是含有前导0，则非法（实际考试可以去掉这个校验试试）
#         if num != 0 and addrs[i][0] == '0':
#             return "invalid IP"
#         # 不在指定范围内, 则抛出异常
#         if num < ranges[i][0] or num > ranges[i][1]:
#             return "invalid IP"
#         # 将十进制数 num 转为十六进制串, 如果十六进制串不足2位, 则补足前导0
#         hexStr = hex(num)[2:]  # hex函数返回值形式为："0xff" 这种, 会带有0x前缀, 从第2位开始截取是为了去掉0x前缀
#         while len(hexStr) < 2:
#             hexStr = '0' + hexStr
#         hexLst.append(hexStr)
#     return int("".join(hexLst), 16)
# if __name__ == '__main__':
#     print(solution(input()))

#68链表中间节点
# head,n = input().split()
# nodes = {}
# for _ in range(int(n)):
#     addr,val,nex =  input().split()
#     nodes[addr] = [val,nex]
# slow = nodes.get(head)
# fast = nodes.get(slow[1])
# while fast is not None:
#     slow = nodes.get(slow[1])
#     fast = nodes.get(fast[1])
#     if fast is  None:
#         break
#     else:
#         fast = nodes.get(fast[1])
# print(slow[0])

#69热点网站统计
# if __name__ == '__main__':
#     count = {}
#
#     while True:
#         try:
#             line = input()
#
#             if not line.isdigit():
#                 count[line] = count.get(line, 0) + 1
#             else:
#                 n = int(line)
#                 print(",".join(map(lambda x: x[0], sorted(count.items(), key=lambda x: (-x[1], x[0]))[:n])))
#         except:
#             break

#70字符串所有整数的最小和
# 输入获取
# s = input()
# 算法入口
# def getResult():
#     isNegative = False
#     negative = []
#     ans = 0
#     for c in s:
#         if '0' <= c <= '9':
#             if isNegative:
#                 negative.append(c)
#             else:
#                 ans += int(c)
#         else:
#             if isNegative and len(negative) > 0:
#                 ans -= int("".join(negative))
#                 negative.clear()
#             isNegative = c == '-'
#     if len(negative) > 0:
#         ans -= int("".join(negative))
#     return ans

#71螺旋数组
# m,n = input().split()
# row =  math.ceil(int(m)/int(n))
# data = []
# for i in range(int(m)):
#     data.append(i)
# num = int(n) * int(row)
# print(num)
# if num > int(m):
#     for _ in range(num - int(m)):
#         data.append('*')
# print(data)
# ans = [[0 for _ in range(int(n))] for _ in range(row)]
# print(ans)
# for i in range()

#72数据分类算法
# n = int(256)
# h = hex(n)
# print(h)
# print(ord('z'))

#73整数编码
# 输入获取
# num = int(input())
# def getLowBitHexStr():
#     # 编码时7位一组，每个字节的低7位用于存储待编码数字的补码
#     lowBit = num & 0b01111111  # 按位与运算, 获取 num 的低7位
#
#     # lowBit的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。
#     if num >> 7 > 0:  # num 右移7位后, 若结果大于0, 则说明后面还有字节
#         lowBit |= 0b10000000  # 按位或运算, 将lowBit最高位置1
#
#     # 编码结果按16进制数的字符格式输出，小写字母需转换为大写字母
#     hexStr = hex(lowBit)[2:].upper()
#     if len(hexStr) == 1:
#         hexStr = "0" + hexStr
#     return hexStr
# def solution():
#     global num
#     result = [getLowBitHexStr()]
#     num >>= 7  # 右移运算移除num的低七位
#     while num > 0:
#         result.append(getLowBitHexStr())
#         num >>= 7  # 右移运算移除num的低七位
#     return ''.join(result)
# print(solution())

#74免单统计
# n = int(input())
# times = [input() for _ in range(n)]
# # 核心代码
# def solution():
#     # 时间升序
#     times.sort()
#     # 免单顾客数量
#     ans = 1
#     # 当前秒的最早时刻
#     last = times[0]
#     lastSecond = last[0:19]
#     for i in range(1, len(times)):
#         cur = times[i]
#         curSecond = cur[0:19]
#         # 同一时刻 或者 不是同一秒
#         if cur == last or curSecond != lastSecond:
#             ans += 1
#             last = cur
#             lastSecond = curSecond
#     return ans

#75字符串加密
# if __name__ == '__main__':
#     n = int(input())
#     # 初始化a数组
#     a = [0] * 50
#     a[0] = 1
#     a[1] = 2
#     a[2] = 4
#     for i in range(3, 50):
#         a[i] = (a[i - 1] + a[i - 2] + a[i - 3]) % 26
#     for _ in range(n):
#         cArr = list(input())
#         # 为字符串的每一位字符添加a[i]偏移量
#         for i in range(len(cArr)):
#             cArr[i] = chr((ord(cArr[i]) + a[i] - 97) % 26 + 97)
#         print("".join(cArr))

#76磁盘容量排序
# import re
# pattern = r"(\d+)([TGM])"
# s= '12G5T3M'
# res = re.findall(pattern, s)
# print(res)
# res.sort(key = lambda x:calc(x))

#77优秀学员统计
# if __name__ == '__main__':
#     input()
#     input()
#
#     # key记录员工id, value记录员工打卡天数
#     freq = {}
#     # key记录员工id，value记录员工第一次打卡是哪天
#     first = {}
#
#     for day in range(30):
#         ids = list(map(int, input().split()))
#
#         for id in ids:
#             freq.setdefault(id, 0)
#             freq[id] += 1
#
#             first.setdefault(id, day)
#
#     # 打卡天数多的员工排在前面, 若打卡天数新题，则首次打卡早的员工排在前面，若首次打卡日期相同，则id小的员工排在前面
#     # 取前5名
#     print(" ".join(map(str, sorted(freq.keys(), key=lambda id: (-freq[id], first[id], id))[:5])))

#78移除数字求最小值
# nums = list(input())
# n = int(input())
#
# stack = []
# length = len(nums)
# remain = length - n
# if length <= n: #数组长度小于移除长度
#     print( "0" )
#     exit()
# for c in nums:
#     while len(stack) > 0 and n > 0 and stack[-1] > c: #栈内有数据，移除次数非0，栈底元素比C大，
#         stack.pop() #移除栈底
#         n -= 1
#     stack.append(c)
#
# while len(stack) > remain:
#         stack.pop()
#
# while stack[0] == '0' and len(stack)!= 1:
#     stack.pop(0)
#
# print(''.join(stack))

#79数组组成的最小数字
# nums = input().split(',')
# def cmp(a,b):
#     s1 = a+b
#     s2 = b+a
#     return 0 if s1 == s2 else 1 if s1 > s2 else -1
# nums.sort(key = lambda x:int(x))
# print(''.join(sorted(nums[:3],key = functools.cmp_to_key(cmp))))

#80传递悄悄话
#父亲节点k,左右孩子为2k+1,2k+2
# times = list(map(int,input().split()))
# ans = 0
# queue = [0]
# while len(queue) > 0:
#     fa = queue.pop(0)
#     print(fa)
#     ch1 = fa * 2 + 1
#     ch2 = fa * 2 + 2
#     ch1_exist = ch1 < len(times) and times[ch1] != -1
#     ch2_exist = ch2 < len(times) and times[ch2] != -1
#
#     if ch1_exist:
#         times[ch1] += times[fa]
#         queue.append(ch1)
#
#     if ch2_exist:
#         times[ch2] += times[fa]
#         queue.append(ch2)
#
#     if not ch1_exist and not ch2_exist:
#         ans = max(ans,times[fa])
#
# print(ans)

#81小朋友分班
# s = list(map(lambda x:x.split('/'),input().split()))
# print(s)
# cls1 = []
# cls2 = []
# isClass1 = False
# n = len(s)
# for i in range(1,n):
#     id, flag = s[i]
#     id = int(id)
#     if id <= 0 or id >= 999:
#         print('ERROR')
#         exit(0)
#     if flag != 'Y' and flag != 'N':
#         print('ERROR')
#         exit(0)
#     if i == 0 and flag == 'Y':
#         print('ERROR')
#         exit(0)
#     if flag == 'Y' and isClass1 or flag == 'N' and not isClass1:
#         cls1.append(id)
#     else:
#         isClass1 = True
#         cls2.append(id)

#82日志排序时间
# import re
# def convert(log):
#     tmp = re.split(r'[.:]', log)
#     H = int(tmp[0]*3600000)
#     M = int(tmp[1]*60000)
#     S = int(tmp[2] * 1000)
#     N = int(tmp[3])
#     return  H+M+S+N
# n = int(input())
# logs = [input() for _ in range(n)]
# logs.sort(key = convert)
# print('\n'.join(logs))

#83比赛评分系统
# M,N = map(int,input().split(','))
# count = [[0] * 11 for _ in range(N+1)]
# countSum = [0] * (N+1)
# for i in range (M):
#     scores = list(map(int,input().split(',')))
#     for j in range(1,N+1):
#         score = scores[j-1]
#         count[j][score] += 1
#         countSum[j] += score
#
# nums = [i for i in range(1,N+1)]
# nums.sort(key = lambda  x: (-countSum[x],[-count[x][y] for y in range(10,0,-1)]))
# print(','.join(map(str,nums[:3])))

#84火星文
# s = input()
# import re
# p = re.compile(r"(\d+)#(\d+)")
# while True:
#     m = p.search(s)
#     print(m)
#     if m:
#         subs = m.group()
#         print(subs)
#         x = int(m.group(1))
#         y = int(m.group(2))
#         s = s.replace(subs,str(4 * x + 3 * y + 2),1)
#     else:
#         break
#
# arr = list(map(int,s.split('$')))
# x = arr[0]
# for y in arr[1:]:
#     x = 2 * x + y + 3
# print(x)

